public class Solution707 {

    int[] next=new int[1005];
    int first=-1;
    int[] val=new int[1005];
    int cur=0;
    int len=0;

    public Solution707() {

    }

    public int get(int index) {
        int p=first;
        int count=0;
        while (p!=-1){
            if (count==index){
                return val[p];
            }
            p=next[p];
            count++;
        }
        return -1;
    }

    public void addAtHead(int val) {
        next[cur]=first;
        first=cur;
        this.val[cur]=val;
        cur++;
        len++;
    }

    public void addAtTail(int val) {
        if (first==-1){
            addAtHead(val);
        }else {
            int p=first;
            while (next[p]!=-1){
                p=next[p];
            }
            next[p]=cur;
            next[cur]=-1;
            this.val[cur]=val;
            cur++;
            len++;
        }
    }

    public void addAtIndex(int index, int val) {
        if (index==0){
            addAtHead(val);
        }else if (index==len){
            addAtTail(val);
        }else if (index<len){
            int p=first;
            int count=0;
            while (p!=-1){
                if (count==index-1){
                    next[cur]=next[p];
                    next[p]=cur;
                    this.val[cur]=val;
                    cur++;
                    len++;
                    return ;
                }
                count++;
                p=next[p];
            }
        }
    }

    public void deleteAtIndex(int index) {
        if (index<len){
            if (index==0) {
                first = next[first];
            }else {
                int p=first;
                int count=0;
                while (p!=-1){
                    if (count==index-1){
                        next[p]=next[next[p]];
                        len--;
                        return ;
                    }
                    count++;
                    p=next[p];
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution707 solution707=new Solution707();
        solution707.addAtHead(7);
        solution707.addAtHead(2);
        solution707.addAtHead(1);
        solution707.addAtIndex(3,0);
        solution707.deleteAtIndex(2);
        solution707.addAtHead(6);
        solution707.addAtTail(4);
        System.out.println(solution707.get(4));
    }
}
